package other;

import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;

// 设计LFU缓存结构

// 最多放 k 条记录
// 空间不足时，就需要根据策略删除一条记录，然后才能加入新记录
// 策略是：哪一个 key 从进入缓存结构的时刻开始，被调用 set 或者 get 的次数最少，就要删掉这个 key
// 如果次数最少的有多个，将调用时间最早的移除
// 要求 get 和 set 的时间复杂度为 O(1)

// 双哈希表
public class D230906 {
    // 双向链表结点结构
    static class Node {
        int freq;
        int key;
        int val;
        //初始化
        public Node(int freq, int key, int val) {
            this.freq = freq;
            this.key = key;
            this.val = val;
        }
    }
    // 哈希表，存储 key-结点
    private HashMap<Integer, Node> mp = new HashMap<>();
    // 哈希表，存储 调用频率-双向链表（存放频率相同的结点）
    private HashMap<Integer, LinkedList<Node>> freq_mp = new HashMap<>();
    // 剩余容量
    private int size = 0;
    // 当前最小频率
    private int min_freq = 0;

    public int[] LFU (int[][] operators, int k) {
        // 构建初始化连接
        // 剩余容量
        this.size = k;
        // 获取操作数据的数量，需要定义一个数组，作为结果返回
        int len = (int) Arrays.stream(operators).filter(x -> x[0] == 2).count();
        int[] res = new int[len];
        // 遍历所有操作
        for (int i = 0, j = 0; i < operators.length; i++) {
            if (operators[i][0] == 1) {
                // set
                set(operators[i][1], operators[i][2]);
            } else {
                // get
                res[j++] = get(operators[i][1]);
            }
        }
        return res;
    }

    private void set(int key, int val) {
        if (mp.containsKey(key)) {
            // key 已经存在，更新 value
            update(mp.get(key), key, val);
        } else {
            // 新的 key
            if (size == 0) {
                // 空间不足，需要删除
                // 根据记录的 最小频率，在第二个哈希表中，获取到该频率的双向链表
                // 删除尾部结点（时间最早调用的）
                int oldkey = freq_mp.get(min_freq).getLast().key;
                freq_mp.get(min_freq).removeLast();
                if (freq_mp.get(min_freq).isEmpty()) {
                    // 若这个链表中没有结点了，就删除该频率
                    freq_mp.remove(min_freq);
                }
                // 删除第一个哈希表中的结点
                mp.remove(oldkey);
            } else {
                size--;
            }
            // 最小频率设置为 1
            min_freq = 1;

            // 第二个哈希表中（频率-双向链表），获取频率为 1 的双向链表（双向链表不存在就创建一个）
            // 在双向链表中，头插该结点
            freq_mp.computeIfAbsent(1, k -> new LinkedList<>()).addFirst(new Node(1, key, val));
            // 将该结点存入第一个哈希表中（key-结点）
            mp.put(key, freq_mp.get(1).getFirst());
        }
    }

    // 已经存在该 key，更新 value 和 调用频率
    private void update(Node node, int key, int val) {
        // 在该频率下的双向链表中，删除该结点
        int freq = node.freq;
        freq_mp.get(freq).remove(node);
        // 如果该频率下的双向链表中，已经没有结点，删除该频率
        if (freq_mp.get(freq).isEmpty()) {
            freq_mp.remove(freq);
            // 若当前频率为最小，最小频率 + 1
            if (min_freq == freq) {
                min_freq++;
            }
        }
        // 将该节点插入 freq + 1 频率下的双向链表，链表不存在就创建链表
        freq_mp.computeIfAbsent(freq + 1, k -> new LinkedList<>()).addFirst(new Node(freq + 1, key, val));
        // 更新第一个哈希表中的值
        mp.put(key, freq_mp.get(freq + 1).getFirst());
    }

    private int get(int key) {
        int res = -1;
        if (mp.containsKey(key)) {
            Node node = mp.get(key);
            res = node.val;
            // 更新频率
            update(node, key, res);
        }
        return res;
    }
}
